<?php


namespace XiaoGuai\DataStructure\Forest\ChildTree;


/**
 * 孩子链表表示法
 * Class ChildLinkedForest
 * @package XiaoGuai\DataStructure\Forest\ChildTree
 */
class ChildLinkedForest
{

    protected $list = [];
    
    public function __construct()
    {
        $this->list = [];
    }


    /**
     * @param array $maps [['data' => null, 'parent' => ''], ...]
     */
    public function create($maps = [])
    {
        // 补上双亲和孩子
        $this->list = [];

        // 先保存node结点
        foreach ($maps as $map) {
            $node = new ChildTreeNode();
            $node->data = $map['data'];
            $node->firstChild = null;
            $this->list[] = $node;
        }

        // 遍历map,将孩子结点放在node的child下面
        foreach ($maps as $i => $map) {
            if ($map['parent'] == -1) {
                // 不是别人的孩子
                continue;
            }
            // 需要挂在其对应的父结点下面
            /* @var $parentNode ChildTreeNode */
            $parentNode = $this->list[$map['parent']];

            // 创建孩子结点
            $childNode = new ChildTreeChildNode();
            $childNode->data = $i; // 孩子结点的下标
            $childNode->next = null;

            // 加到父结点后面
            if (is_null($parentNode->firstChild)) {
                $parentNode->firstChild = $childNode;
            } else {
                // 找到最后一个child结点,放到其后面
                $p = $parentNode->firstChild;
                while (!is_null($p->next)) {
                    $p = $p->next;
                }
                $p->next = $childNode;
            }

            // 类是引用传递
            $this->list[$map['parent']] = $parentNode;
        }
    }
}